﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<unordered_map>
#include<stack>
#include<map>
#include<queue>
#include<set>

using namespace std;
/*
	双指针：对撞指针/快慢指针

	(1). 对撞指针：?般?于顺序结构中，也称左右指针。
		? 对撞指针从两端向中间移动。?个指针从最左端开始，另?个从最右端开始，然后逐渐往中间逼近。
		? 对撞指针的终?条件?般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
			? left == right  （两个指针指向同?个位置） 
			? left > right  （两个指针错开）
	(2). 快慢指针：这种?法对于处理环形链表或数组?常有?。其实不单单是环形链表或者是数组。
		  快慢指针的实现?式有很多种，最常?的?种就是：
		? 在?次循环中，每次让慢的指针向后移动?位，?快的指针往后移动两位，实现?快?慢

*/

// 1.移动零：快排的思想：数组划分区间 - 数组分两块
// 2.复写零：从后往前(涉及到覆盖的)
// 3.快乐数：快慢指针(设计循环)
// 4.盛水最多的容器：对撞指针
// 5.有效三角的个数：固定一边+对撞指针
// 6.和为S的两个数字：排序+对撞指针
// 7.三数之和：排序+对撞指针+固定
// 8.四数之和：排序+对撞指针(三指针)+固定

//vector<int> ret;//存储结果
//vector<int> index;//记录 nums 中当前元素的原始下标
//int tmpindex[100010];
//int tmpnums[100010];
//    void mergeSort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right)return;
//        int mid = left + ((right - left) >> 1);
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//        int cur1 = left, cur2 = mid + 1, i = 0;
//        while (cur1 <= mid && cur2 <= right)
//        {
//            if (nums[cur1] <= nums[cur2])
//            {
//                tmpnums[i] = nums[cur2];
//                tmpindex[i] = index[cur2];
//                i++;
//                cur2++;
//            }
//            else
//            {
//                ret[index[cur1]] += right - cur2 + 1;
//                tmpnums[i] = nums[cur1];
//                tmpindex[i] = index[cur1];
//                i++;
//                cur1++;
//            }
//        }
//        while (cur1 <= mid)
//        {
//            tmpnums[i] = nums[cur1];
//            tmpindex[i] = index[cur1];
//            i++;
//            cur1++;
//        }
//        while (cur2 <= right)
//        {
//            tmpnums[i] = nums[cur2];
//            tmpindex[i] = index[cur2];
//            i++;
//            cur2++;
//        }
//        for (int i = left; i <= right; i++)
//        {
//            nums[i] = tmpnums[i - left];
//            index[i] = tmpindex[i - left];
//        }
//    }
    //vector<int> countSmaller(vector<int>& nums)
    //{
    //    ret.resize(nums.size());
    //    index.resize(nums.size());
    //    for (int i = 0; i < nums.size(); i++) index[i] = i;
    //    mergeSort(nums, 0, nums.size() - 1);
    //    return ret;
    //}




//struct ListNode {
//    int val;
//    ListNode* next;
//    ListNode() : val(0), next(nullptr) {}
//    ListNode(int x) : val(x), next(nullptr) {}
//    ListNode(int x, ListNode* next) : val(x), next(next) {}
//};
//
//ListNode* reverseKGroup(ListNode* head, int k)
//{
//    ListNode* cur = head;
//    int cnt = 0;
//    while (cur)
//    {
//        cur = cur->next;
//        cnt++;
//    }
//    int ret = cnt / k;
//    ListNode* newhead = new ListNode(0);
//    ListNode* prev = newhead, * cur1 = head;
//    for (int i = 0; i < ret; i++)
//    {
//        ListNode* tmp = cur1;
//        for (int j = 0; j < k; j++)
//        {
//            ListNode* cur2 = cur1->next;
//            cur1->next = prev->next;
//            prev->next = cur1;
//            cur1 = cur2;
//        }
//        prev = tmp;
//    }
//    prev->next = cur1;
//    ListNode* dest = newhead->next;
//    delete newhead;
//    return dest;
//}
//struct cmp
//{
//    bool operator()(int t1, int t2)
//    {
//        return t1 < t2;
//    }
//};
//class MedianFinder
//{
//    priority_queue<int, vector<int>, less<int>> left;//大根堆
//    priority_queue<int, vector<int>, greater<int>> right;//小根堆
//public:
//    MedianFinder()
//    {}
//
//    void addNum(int num)
//    {
//        int n = left.size(), m = right.size();
//        if (n == m || n == 0)
//        {
//            if (num > left.top())
//            {
//                left.push(right.top());
//                right.pop();
//                right.push(num);
//            }
//            else left.push(num);
//        }
//        else if (n > m)
//        {
//            if (num <= left.top())
//            {
//                right.push(left.top());
//                left.pop();
//                left.push(num);
//            }
//            else right.push(num);
//        }
//    }
//
//    double findMedian()
//    {
//        if (left.size() == right.size())
//            return (left.top() + right.top()) / 2;
//        else return left.top();
//    }
//};
//int main()
//{
//    //vector<int> arr{ 1,0,1,1 };
//    //vector<string> v{ "foo","bar" };
//   // string s = "croakcroa";
//    /*countSmaller(arr);*/
//    /*TreeNode* head1 = new TreeNode(1);
//    TreeNode* head2 = new TreeNode(2);
//    TreeNode* head3 = new TreeNode(3);
//    TreeNode* head4 = new TreeNode(3);
//    TreeNode* head5 = new TreeNode(5);
//    TreeNode* head9 = new TreeNode(9);
//    head1->left = head3;
//    head1->right = head2;
//    head3->left = head5;
//    head3->right = head4;
//    head2->right = head9;*/
//   //vector<string> v{ "flower","flow","flight" };
//   string s = "babad";
//   string a = "3[a10[bc]]", b = "ad#c";
//   vector<int> v1{ 1,2,3,4,5 };
//   vector<string> v2{ "the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is" };
//   //topKFrequent(v2,4);
//   MedianFinder* obj = new MedianFinder();
//   obj->addNum(1);
//   obj->addNum(2);
//   double param_2 = obj->findMedian();
//   obj->addNum(3);
//   double param_3 = obj->findMedian();
//}



//vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
//{
//    vector<int> cs(numCourses);
//    //创建邻接表+入度
//    unordered_map<int, vector<int>> edges;
//    vector<int> in(numCourses);
//
//    for (auto& e : prerequisites)
//    {
//        int a = e[0], b = e[1];
//        edges[b].push_back(a);
//        in[a]++;
//    }
//
//    //遍历查找入度为0的点加入到队列
//    queue<int> q;
//    for (int i = 0; i < numCourses; i++)
//    {
//        if (in[i] == 0)q.push(i);
//    }
//
//    //循环
//    while (!q.empty())
//    {
//        int sz = q.size();
//        while (sz--)
//        {
//            auto tmp = q.front();
//            q.pop();
//            cs.push_back(tmp);
//            for (auto& e : edges[tmp])
//            {
//                if (--in[e] == 0)q.push(e);
//            }
//        }
//    }
//
//    //判环
//    for (int i = 0; i < numCourses; i++)
//    {
//        if (in[i])
//        {
//            cs.clear();
//        }
//    }
//    return cs;
//}
//int main()
//{
//    vector<vector<int>> vv{ {1,0} };
//
//    findOrder(2, vv);
//}






vector<string> vv;
string path;
string hash1[15];
    vector<string> letterCombinations(string digits)
    {
        int i = 2;
        for (char ch = 'a'; ch <= 'v'; )
        {
            string s;
            int tmp = 3;
            while (tmp--)s += ch++;
            hash1[i++] = s;
        }
        return vv;
    }
    int main()
    {
        letterCombinations("23");
 }





    ////////多源BFS和BFS解决拓扑排序
    ////1.01 矩阵
    class Solution {
    int n, m;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        n = mat.size(); m = mat[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> vv(n, vector<int>(m, -1));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 0)
                {
                    vv[i][j] = 0;
                    q.push({ i,j });
                }
            }
        }
        int cnt = 0;
        while (!q.empty())
        {
            int sz = q.size();
            cnt++;
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && vv[x][y] == -1)
                    {
                        vv[x][y] = cnt;
                        q.push({ x,y });
                    }
                }
            }
        }
        return vv;
    }
};



    ////2.⻜地的数量
    class Solution {
        int n, m;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        int vis[510][510] = { 0 };
        int ret = 0;
    public:
        int numEnclaves(vector<vector<int>>& grid)
        {
            n = grid.size(), m = grid[0].size();
            queue<pair<int, int>> q;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (grid[i][j] == 1)ret++;
            for (int i = 0; i < n; i++)
            {
                if (grid[i][0] == 1 && !vis[i][0])
                {
                    q.push({ i,0 });
                    vis[i][0] = 1;
                    ret--;
                }
                if (grid[i][m - 1] == 1 && !vis[i][m - 1])
                {
                    q.push({ i,m - 1 });
                    vis[i][m - 1] = 1;
                    ret--;
                }
            }
            for (int i = 0; i < m; i++)
            {
                if (grid[0][i] == 1 && !vis[0][i])
                {
                    q.push({ 0,i });
                    vis[0][i] = 1;
                    ret--;

                }
                if (grid[n - 1][i] == 1 && !vis[n - 1][i])
                {
                    q.push({ n - 1,i });
                    vis[n - 1][i] = 1;
                    ret--;
                }
            }
            while (!q.empty())
            {
                int sz = q.size();
                while (sz--)
                {
                    auto [a, b] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y])
                        {
                            q.push({ x,y });
                            vis[x][y] = 1;
                            ret--;
                        }
                    }
                }
            }
            return ret;
        }
    };






    ////3.地图中的最⾼点
    class Solution {
        int n, m;
        int dx[4] = { 0,0,-1,1 };
        int dy[4] = { 1,-1,0,0 };
    public:
        vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
        {
            n = isWater.size(); m = isWater[0].size();
            vector<vector<int>> height(n, vector<int>(m, -1));
            queue<pair<int, int>> q;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (isWater[i][j] == 1)
                    {
                        height[i][j] = 0;
                        q.push({ i,j });
                    }
                }
            }
            int cnt = 0;
            while (!q.empty())
            {
                int sz = q.size();
                cnt++;
                while (sz--)
                {
                    auto [a, b] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < n && y >= 0 && y < m && height[x][y] == -1)
                        {
                            height[x][y] = cnt;
                            q.push({ x,y });
                        }
                    }
                }
            }
            return height;
        }
    };




    ////4. 地图分析
    class Solution {
        int n;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        int maxlen = 0, cnt = 0;;
        int vis[110][110] = { 0 };
    public:
        int maxDistance(vector<vector<int>>& grid)
        {
            n = grid.size();
            queue<pair<int, int>> q;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] == 1)
                    {
                        vis[i][j] = 1;
                        q.push({ i,j });
                    }
                }
            }
            if (q.size() == 0 || q.size() == n * n)return -1;
            while (!q.empty())
            {
                int sz = q.size();
                cnt++;
                while (sz--)
                {
                    auto [a, b] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y])
                        {
                            q.push({ x,y });
                            vis[x][y] = 1;
                            maxlen = max(maxlen, cnt);
                        }
                    }
                }
            }
            return maxlen;
        }
    };






 ////////BFS解决拓扑排序
    ////1.课程表
    class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
        {
            //1.创建邻接表
            unordered_map<int, vector<int>> edges;
            //入度
            vector<int> in(numCourses);
            for (auto& e : prerequisites)
            {
                int a = e[0], b = e[1];
                edges[b].push_back(a);
                in[a]++;
            }
            //将入度为0的点插入到队列中
            queue<int> q;
            for (int i = 0; i < numCourses; i++)
            {
                if (in[i] == 0)
                    q.push(i);
            }
            //循环
            while (!q.empty())
            {
                int sz = q.size();
                while (sz--)
                {
                    auto tmp = q.front();
                    q.pop();
                    for (auto& e : edges[tmp])//找到对应的点将入度--
                    {
                        if (--in[e] == 0)q.push(e);//判断入度是否为0，为0则加入队列
                    }
                }
            }
            //判断一下入度是否都为0，如果都为0则表示没有环可以完成，否则有环
            for (int i = 0; i < numCourses; i++)
            {
                if (in[i])return false;
            }
            return true;
        }
    };




    ////2.课程表 II
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
        {
            vector<int> cs;
            //创建邻接表+入度
            unordered_map<int, vector<int>> edges;
            vector<int> in(numCourses);

            for (auto& e : prerequisites)
            {
                int a = e[0], b = e[1];
                edges[b].push_back(a);
                in[a]++;
            }

            //遍历查找入度为0的点加入到队列
            queue<int> q;
            for (int i = 0; i < numCourses; i++)
            {
                if (in[i] == 0)q.push(i);
            }

            //循环
            while (!q.empty())
            {
                int sz = q.size();
                while (sz--)
                {
                    auto tmp = q.front();
                    q.pop();
                    cs.push_back(tmp);
                    for (auto& e : edges[tmp])
                    {
                        if (--in[e] == 0)q.push(e);
                    }
                }
            }

            //判环
            for (int i = 0; i < numCourses; i++)
            {
                if (in[i])
                {
                    cs.clear();
                }
            }
            return cs;
        }
    };



    ////3.⽕星词典
    class Solution {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int>in;
        bool check = false;
    public:
        void Add(const string& s1, const string& s2)
        {
            int n = min(s1.size(), s2.size());
            int i = 0;
            for (i = 0; i < n; i++)
            {
                if (s1[i] != s2[i])
                {
                    char a = s1[i], b = s2[i];
                    if (!edges.count(a) || !edges[a].count(b))
                    {
                        edges[a].insert(b);
                        in[b]++;
                    }
                    break;
                }
            }
            if (i == s2.size() && i < s1.size())check = true;//s1="abc"  s2="ab" 是不合法的将check设置为true
        }
        string alienOrder(vector<string>& words)
        {
            string s;
            for (auto& s : words)
            {
                for (auto& ch : s)
                    in[ch] = 0;
            }
            for (int i = 0; i < words.size(); i++)
            {
                for (int j = i + 1; j < words.size(); j++)
                {
                    Add(words[i], words[j]);
                    if (check)return "";//check==true直接返回空字符不合法即可
                }
            }
            queue<char> q;
            for (auto [a, b] : in)
            {
                if (b == 0)q.push(a);
            }
            while (!q.empty())
            {
                int sz = q.size();
                while (sz--)
                {
                    auto tmp = q.front();
                    q.pop();
                    s += tmp;
                    for (auto& e : edges[tmp])
                    {
                        if (--in[e] == 0)q.push(e);
                    }
                }
            }
            for (auto [a, b] : in)
            {
                if (b)return "";
            }
            return s;
        }
    };






    ////////队列+宽搜
    ////1.N 叉树的层序遍历
    /*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

    class Solution {
    public:
        vector<vector<int>> levelOrder(Node* root)
        {
            vector<vector<int>> vv;
            vector<int> v;
            if (root == nullptr)return vv;
            queue<Node*> q;
            q.push(root);
            while (!q.empty())
            {
                int sz = q.size();//统计本层节点个数
                while (sz--)
                {
                    Node* tmp = q.front();
                    v.push_back(tmp->val);
                    q.pop();
                    for (auto& e : tmp->children)//逐次加入孩子节点
                    {
                        if (e != nullptr)
                            q.push(e);
                    }
                }
                vv.push_back(v);
                v.clear();
            }
            return vv;
        }
    };




    ////2. ⼆叉树的锯⻮形层序遍历
    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root)
        {
            vector<vector<int>> vv;
            vector<int> v;
            if (root == nullptr)return vv;
            int cnt = 0;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty())
            {
                cnt++;
                int sz = q.size();
                while (sz--)
                {
                    TreeNode* tmp = q.front();
                    q.pop();
                    v.push_back(tmp->val);
                    if (tmp->left != nullptr)q.push(tmp->left);
                    if (tmp->right != nullptr)q.push(tmp->right);
                }
                if (cnt % 2 == 0)reverse(v.begin(), v.end());
                vv.push_back(v);
                v.clear();
            }
            return vv;
        }
    };





    ////3.⼆叉树最⼤宽度
    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
    class Solution {
    public:
        int widthOfBinaryTree(TreeNode* root)
        {
            queue<pair<TreeNode*, unsigned int>> q;
            q.push(make_pair(root, 1));
            unsigned int cnt = 0;
            while (!q.empty())
            {
                int sz = q.size();
                cnt = max(q.back().second - q.front().second + 1, cnt);
                while (sz--)
                {
                    TreeNode* tmp = q.front().first;
                    unsigned int ret = q.front().second;
                    q.pop();
                    if (tmp->left != nullptr)
                    {
                        q.push(make_pair(tmp->left, 2 * ret));
                    }
                    if (tmp->right != nullptr)
                    {
                        q.push(make_pair(tmp->right, 2 * ret + 1));
                    }
                }
            }
            return cnt;
        }
    };
    --------------------------------------------------------------------------------------------
        //用数组模拟队列
        /**
         * Definition for a binary tree node.
         * struct TreeNode {
         *     int val;
         *     TreeNode *left;
         *     TreeNode *right;
         *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
         *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
         *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
         * };
         */
        class Solution {
        public:
            int widthOfBinaryTree(TreeNode* root)
            {
                vector<pair<TreeNode*, unsigned int>> v;
                v.push_back({ root,1 });
                unsigned int cnt = 0;
                while (v.size())
                {
                    auto& [x1, y1] = v[0];
                    auto& [x2, y2] = v.back();
                    cnt = max(cnt, y2 - y1 + 1);
                    vector<pair<TreeNode*, unsigned int>> tmp;
                    for (auto& [x, y] : v)
                    {
                        if (x->left)tmp.push_back({ x->left,2 * y });
                        if (x->right)tmp.push_back({ x->right,2 * y + 1 });
                    }
                    v = tmp;
                }
                return cnt;
            }
    };





    ////4.在每个树⾏中找最⼤值
    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
    class Solution {
    public:
        vector<int> largestValues(TreeNode* root)
        {
            vector<int> v;
            if (root == nullptr)return v;
            queue<TreeNode*> q;
            q.push(root);
            int maxnum = INT_MIN;
            while (!q.empty())
            {
                int sz = q.size();
                while (sz--)
                {
                    TreeNode* tmp = q.front();
                    maxnum = max(maxnum, tmp->val);
                    q.pop();
                    if (tmp->left)
                        q.push(tmp->left);
                    if (tmp->right)
                        q.push(tmp->right);
                }
                v.push_back(maxnum);
                maxnum = INT_MIN;
            }
            return v;
        }
    };





    ///////优先级队列
    ////1.前 K 个⾼频单词
    class Solution {
        typedef pair<string, int> PII;
    public:
        struct cmp
        {
            bool operator()(const PII& p1, const PII& p2)
            {
                if (p1.second == p2.second)
                    return p1.first < p2.first;// 频次相同，字典序按照⼤根堆的⽅式排列
                return p1.second > p2.second;
            }
        };
        vector<string> topKFrequent(vector<string>& words, int k)
        {
            priority_queue<PII, vector<PII>, cmp> pq;
            vector<string> v(k);
            unordered_map<string, int> hash;
            for (auto& e : words)hash[e]++;
            for (auto& e : hash)
            {
                pq.push(e);
                if (pq.size() > k)pq.pop();
            }
            for (int i = k - 1; i >= 0; i--)
            {
                v[i] = pq.top().first;
                pq.pop();
            }
            return v;
        }
    };




    ////2.数据流的中位数
    class MedianFinder
    {
        priority_queue<int, vector<int>, less<int>> left;//大根堆
        priority_queue<int, vector<int>, greater<int>> right;//小根堆
    public:
        MedianFinder()
        {}

        void addNum(int num)
        {
            int n = left.size(), m = right.size();
            if (n == m)
            {
                if (!left.empty() && num > left.top())
                {
                    right.push(num);
                    left.push(right.top());
                    right.pop();
                }
                else left.push(num);
            }
            else if (n > m)
            {
                if (num <= left.top())
                {
                    right.push(left.top());
                    left.pop();
                    left.push(num);
                }
                else right.push(num);
            }
        }

        double findMedian()
        {
            if (left.size() == right.size())
                return (left.top() + right.top()) / 2.0;
            else return left.top();
        }
    };

    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder* obj = new MedianFinder();
     * obj->addNum(num);
     * double param_2 = obj->findMedian();
     */






    ////////栈
    ////1.删除字符串中的所有相邻重复项
    class Solution {
    public:
        string removeDuplicates(string s)
        {
            stack<char> st;
            for (int i = 0; i < s.size(); i++)
            {
                if (st.empty())st.push(s[i]);
                else
                {
                    if (st.top() == s[i])
                    {
                        st.pop();
                        continue;
                    }
                    else
                        st.push(s[i]);
                }
            }
            string str;
            while (!st.empty())
            {
                str += st.top();
                st.pop();
            }
            reverse(str.begin(), str.end());
            return str;
            ------------------------------------------------------------------------------------------------
                //模拟栈
                string ret;
            for (auto& e : s)
            {
                if (ret.size() && e == ret.back())ret.pop_back();
                else ret += e;
            }
            return ret;
        }
    };





    ////2.⽐较含退格的字符串
    class Solution {
    public:
        bool backspaceCompare(string s, string t)
        {
            stack<char>st1, st2;
            for (auto& e : s)
            {
                if (e != '#')st1.push(e);
                else
                {
                    if (!st1.empty())st1.pop();
                }
            }
            for (auto& e : t)
            {
                if (e != '#')st2.push(e);
                else
                {
                    if (!st2.empty())st2.pop();
                }
            }
            if (st1.size() != st2.size())return false;
            while (!st1.empty())
            {
                if (st1.top() == st2.top())
                {
                    st1.pop(); st2.pop();
                }
                else return false;
            }
            return true;
        }
    };
    -------------------------------------------------------------------------------------------- -

        class Solution {
        public:
            string backspaceCompare(string& str)
            {
                string s;
                for (auto& e : str)
                {
                    if (e != '#')s += e;
                    else
                    {
                        if (s.size())s.pop_back();
                    }
                }
                return s;
            }
            bool backspaceCompare(string s, string t)
            {
                return backspaceCompare(s) == backspaceCompare(t);
            }
    };





    ////3.基本计算器 II
    class Solution {
    public:
        int calculate(string s)
        {
            stack<int> st;
            char op = '+';
            for (int i = 0; i < s.size();)
            {
                int tmp = 0;
                if (s[i] == ' ')i++;
                else if (s[i] >= '0' && s[i] <= '9')
                {
                    while (i < s.size() && (s[i] >= '0' && s[i] <= '9'))
                        tmp = tmp * 10 + (s[i++] - '0');
                    if (op == '+') st.push(tmp);
                    else if (op == '-') st.push(-tmp);
                    else if (op == '*')st.top() *= tmp;
                    else st.top() /= tmp;
                }
                else op = s[i++];
            }
            int sum = 0;
            while (!st.empty())
            {
                sum += st.top();
                st.pop();
            }
            return sum;
        }
    };
    ----------------------------------------------------------------------------------------
        //数组模拟栈
        class Solution {
        public:
            int calculate(string s)
            {
                vector<int> v;
                char op = '+';
                for (int i = 0; i < s.size();)
                {
                    int tmp = 0;
                    if (s[i] == ' ')i++;
                    else if (s[i] >= '0' && s[i] <= '9')
                    {
                        while (i < s.size() && (s[i] >= '0' && s[i] <= '9'))
                            tmp = tmp * 10 + (s[i++] - '0');
                        if (op == '+') v.push_back(tmp);
                        else if (op == '-') v.push_back(-tmp);
                        else if (op == '*')v.back() *= tmp;
                        else v.back() /= tmp;
                    }
                    else op = s[i++];
                }
                int sum = 0;
                for (auto& e : v)sum += e;
                return sum;
            }
    };




    ////4.字符串解码
    class Solution {
    public:
        string decodeString(string s)
        {
            stack<int> st1;
            stack<string> st2;
            for (int i = 0; i < s.size();)
            {
                if (s[i] - '0' >= 0 && s[i] - '0' <= 9)
                {
                    int tmp = 0;
                    while (i < s.size() && (s[i] - '0' >= 0 && s[i] - '0' <= 9))
                    {
                        tmp = tmp * 10 + (s[i++] - '0');
                    }
                    st1.push(tmp);
                }
                else if (s[i] == '[' || (s[i] >= 97 && s[i] <= 122))
                {
                    string tmp;
                    if (s[i] == '[')
                    {
                        tmp += '[';
                        st2.push(tmp);
                        i++;
                    }
                    else
                    {
                        while (i < s.size() && (s[i] >= 97 && s[i] <= 122))
                        {
                            tmp += s[i++];
                        }
                        st2.push(tmp);
                    }
                }
                else
                {
                    string str;
                    while (st2.top() != "[")
                    {
                        string tmp = st2.top();
                        st2.pop();
                        str.insert(0, tmp);
                    }
                    if (st2.top() == "[")st2.pop();//删除"]"
                    int ret = st1.top();
                    st1.pop();
                    string ss;
                    while (ret--)
                    {
                        ss += str;
                    }
                    st2.push(ss);
                    i++;
                }
            }
            vector<string>v;
            string str;
            while (!st2.empty())
            {
                v.push_back(st2.top());
                st2.pop();
            }
            for (int i = v.size() - 1; i >= 0; i--)
                str += v[i];
            return str;
        }
    };





    ////////字符串
    ////1.最⻓公共前缀
    class Solution {
    public:
        string maxCommonPrefix(string& s1, string& s2)
        {
            int minlen = s1.size() < s2.size() ? s1.size() : s2.size();
            string s;
            for (int i = 0; i < minlen; i++)
            {
                if (s1[i] == s2[i])s += s1[i];
                else break;
            }
            return s;
        }
        string longestCommonPrefix(vector<string>& strs)
        {
            string s = strs[0];
            for (int i = 1; i < strs.size(); i++)
            {
                s = maxCommonPrefix(s, strs[i]);
            }
            return s;
        }
    };
    --------------------------------------------------------------------------------------------
        class Solution {
        public:
            string longestCommonPrefix(vector<string>& strs)
            {
                for (int i = 0; i < strs[0].size(); i++)
                {
                    char tmp = strs[0][i];
                    for (int j = 1; j < strs.size(); j++)
                    {
                        if (i == strs[j].size() || tmp != strs[j][i])return strs[j].substr(0, i);
                    }
                }
                return strs[0];
            }
    };



    ////2.最⻓回⽂⼦串
    class Solution {
    public:
        string longestPalindrome(string s)
        {
            //固定一个下标
            int begin = 0, len = 0;
            int left = 0, right = 0;
            for (int i = 0; i < s.size(); i++)
            {
                left = i, right = i;
                //做一次奇数长度扩展
                while (left >= 0 && right < s.size() && s[left] == s[right])
                {
                    left--; right++;
                }
                if (right - left - 1 > len)
                {
                    len = right - left - 1;
                    begin = left + 1;
                }
                //偶数长度扩展
                left = i, right = i + 1;
                while (left >= 0 && right < s.size() && s[left] == s[right])
                {
                    left--; right++;
                }
                if (right - left - 1 > len)
                {
                    len = right - left - 1;
                    begin = left + 1;
                }
            }
            return s.substr(begin, len);
        }
    };




    ////3.⼆进制求和
    class Solution {
    public:
        string addBinary(string a, string b)
        {
            string ret;
            int n = a.size() - 1, m = b.size() - 1;
            int sum = 0;
            while (n >= 0 || m >= 0 || sum)
            {
                if (n >= 0)sum += a[n--] - '0';
                if (m >= 0)sum += b[m--] - '0';
                ret += to_string(sum % 2);
                sum /= 2;
            }
            reverse(ret.begin(), ret.end());
            return ret;
        }
    };




    ////4.字符串相乘
    class Solution {
    public:
        string multiply(string num1, string num2)
        {
            //无进位相乘再相加
            int n = num1.size(), m = num2.size();
            vector<int> v(n + m - 1);
            reverse(num1.begin(), num1.end());
            reverse(num2.begin(), num2.end());
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    int tmp = (num1[j] - '0') * (num2[i] - '0');
                    v[i + j] += tmp;
                }
            }
            int tmp = 0, t = 0;
            string s;
            while (tmp < n + m - 1 || t)
            {
                if (tmp < n + m - 1)t += v[tmp++];
                s += (t % 10) + '0';
                t /= 10;
            }
            while (s.size() > 1 && s.back() == '0')
                s.pop_back();
            reverse(s.begin(), s.end());
            return s;
        }
    };

